import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list=new LinkedList<>();
        HashMap<Integer,Integer> map=new HashMap<>();
        if(candidates.length==0){
            return list;
        }
        map.put(0,1);
        int sum=0;
        for(int num:candidates){
            sum=sum+num;
            map.put(sum,num);
        }
        for(int num:candidates){
            int len=target-num;
            if(map.containsKey(len)){
                List<Integer>arr=new LinkedList<>();
                arr.add(num);
                while(map.containsKey(len)&&len!=0){
                    arr.add(map.get(len));
                    len=len-map.get(len);
                }
                list.add(arr);
            }
        }
        return list;
    }
    public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        int len=0;
        for(int num:nums){
            int count=0;
            int curnum=0;
            if(!set.contains(num-1)){
                count=1;
                curnum=num;
            }
            while(set.contains(curnum+1)){
                count++;
                curnum++;;
            }
            len=Math.max(len,count);
        }
        return len;
    }

    public int maxProfit(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int max=0;
        for(int i=0;i<prices.length;i++){
            for(int j=i+1;j<prices.length;j++){
                   if(prices[j]>prices[i]){
                       int len=prices[j]-prices[i];
                       if(len>max){
                           max=len;
                       }
                   }
            }
        }
  return max;
    }
}